1. Field of the Invention
This application relates generally to packet switching devices or systems, e.g., routers, switches, combination routers/switches, components thereof, etc., and, specifically, to methods in such devices or systems of performing table lookup operations through accesses to content addressable memories (“CAMs”).
2. Related Art
Content addressable memories (“CAMs”) are a convenient mechanism for performing table lookup operations in packet switching devices or systems such as routers, switches and combination routers/switches. Such table lookup operations are useful, for example, in making packet classification and forwarding decisions at high speed. In performing these table lookup operations, the device or system typically derives a table lookup index from one or more packet fields, and inputs that index to a CAM system, i.e., typically a CAM and an associated RAM, having a plurality of entries, each having a key portion and a content portion. In response, the CAM system returns one or more matching entries, i.e., entries having a key portion that matches the inputted table index. The packet classification and forwarding decision for the packet is then made responsive to the content portion of the one or more matching entries.
A problem arises when the size of the table lookup index exceeds the maximum size of the key that is input to the CAM system. Such a problem is likely to arise, for example, in IPv6 compliant packet switching devices or systems where it is desirable to make forwarding and classification decisions based on the combination of certain packet fields, e.g., IP source address, IP destination address, etc., that together have a size that exceeds the maximum desirable key size, e.g., 144 bits, of available ternary (or binary) CAMs that are cost effective for the application. This problem is particularly likely to arise in IPv6 compliant devices or systems because of the increased size of the IP source and address fields (128 bits) compared to that in IPv4 complaint devices or systems (32 bits). In such applications, more expensive CAMs having a larger key size, e.g., 576 bits, can be used to accommodate the desired table index size, but only at the expense of increased system cost.